class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((int[] a, int[] b)-> a[0]!=b[0]?b[0]-a[0]:b[1]-a[1]);

        for (int i = 0; i < k; ++i) {
            pq.offer(new int[]{nums[i], i});
        }

        int[] ans = new int[n-k+1];
        ans[0] = pq.peek()[0];
        for (int i = k; i < n; ++i) {
            pq.offer(new int[]{nums[i], i});

            // 如果最大值在不在窗口范围内，删掉
            while (pq.peek()[1] <= i-k) {
                pq.poll();
            }
            ans[i-k+1] = pq.peek()[0];
        }
        return ans;
    }
}